/*
 * @Author: your name
 * @Date: 2024-03-31 10:39:45
 * @LastEditTime: 2024-03-31 10:58:22
 * @LastEditors: Please set LastEditors
 * @Description: In User Settings Edit
 * @FilePath: \.leetcode\160.相交链表.cpp
 */
/*
 * @lc app=leetcode.cn id=160 lang=cpp
 *
 * [160] 相交链表
 */

// @lc code=start
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        // 计算listA和listB的长度
        int lenA = 0;
        int lenB = 0;
        ListNode* curA = headA;
        while(curA != nullptr){
            lenA++;
            curA = curA->next;
        }
        ListNode* curB = headB;
        while(curB != nullptr){
            lenB++;
            curB = curB->next;
        }
        curA = headA;
        curB = headB;
        if (lenA >= lenB)
        {
            // 长度差
            int sub = lenA-lenB;
            while(sub--){
                curA = curA->next;
            }

        }
        else{
            // 长度差
            int sub = lenB - lenA;
            while(sub--){
                curB = curB->next;
            }
        }
        while(curA != nullptr && curB != nullptr){
            if(curA == curB){
                return curA;
            }
            else{
                curA = curA->next;
                curB = curB->next;
            }
        }
        return nullptr;
        
    }
};
// @lc code=end


// 先求出2条链表的长度差，然后长的再移动cur指针至两条链表一样长，
// 接着同步往下移动，然后判断是不是同一个指针即可。